package com.cctc.juc.source.Bitc.Icontainer.hash;
/**
 * 【哈希表】
 * 1. 概述：哈希表本质上就是一个数组，首先基于散列函数，计算关键字（Key）的散列值，然后对数组长度进行取模 [hash(key) % n] 运算，得到元素在数组中存放的位置，以此达到访问数组中的元素的目的。
 * - 此外，基于哈希函数的哈希表，天然具备 [去重、判重、频次统计] 的特性，即相同输入的哈希值一定相同，不同哈希值的输入一定不同，首先基于 hash(key) % n 进行地址，然后基于 hash(key) / n 进行（Key）重复判断，最后使用元素值（Value）计算重复次数，进行频次统计。
 * 2. 优势：基于数组寻址特点，加快元素查找的速度，时间复杂度为 O(1)。
 * 3. 哈希函数：将任意长度的输入通过哈希运算后，（压缩）映射成一个固定长度的输出，该输出值就是哈希（散列）值。
 * - 本质上来说，哈希函数就是找到一种数据内容和数据存放地址之间的映射关系。
 * 3.1）哈希函数的要求：计算快、散列值数位分布均匀。
 * 3.1）常见的哈希函数：直接定址、除留取余、平方取中、随机数、乘法哈希、数字分析等。
 * 例如 HashMap 中采用的就是数字分析（对关键字 [Key] 进行数字分析，尽量选出均匀分布的几位作为散列地址）。
 * - 哈希算法：键 key 的哈希码高 16 位不变，低 16 位与高 16 位进行异或，作为键 key 的哈希值。
 * 即取 int 类型的一半，刚好可以将该二进制数对半切开，再异或（同 0 异 1）打散，减少哈希冲突。
 * 然后使用打散的哈希值，定位 table 数组的下标（哈希槽）= hash & [n - 1]。
 * 即 table 数组的下标只与（打散的）哈希值的低 n 位有关，散列性较好，冲突较低。
 * 4. 哈希冲突：基于散列函数，对关键字（Key）进行散列运算后，得到元素在数组中存放的位置是相同的，就造成了哈希冲突或哈希碰撞。
 * - 哈希碰撞的概率越小，哈希表存取的效率就越高。
 * 哈希冲突解决方案：开放地址、链（接）地址。
 * 1）开放地址：当冲突发生时，使用某种探测算法寻找数组中下一个可用的地址。
 * 探测算法：线程探测、双向探测、双哈希函数探测。
 * - 线程探测：步长为 1，依次向后，直到寻找到下一个可用的地址。
 * - 双向探测：步长为一个增量，+ / - 增量，直到寻找到下一个可用的地址。
 * - 双哈希函数探测：步长为另外一个哈希函数计算出的值，直到寻找到下一个可用的地址。
 * 问题：通过持续探测，最终找到下一个可用的位置，解决冲突的效率偏低。
 * 2）链（接）地址：当冲突发生时，使用链表（或红黑树）将发生冲突的元素链接在一起。
 * 特点：解决冲突的效率较高，但却（稍微）影响了元素查找的效率，查找复杂度为链表长度 O(m) 或红黑树深度 O(logm)。
 * 5. 哈希表的体系结构：
 * 1）普通哈希表
 * - Map -> AbstractMap -> [核心] HashMap -> LinkedHashMap；
 * - Map -> SortedMap -> TreeMap；
 * 2）使用线程同步方式（“线程排队 [同步队列]”、“热点分散 [分段锁]” 等）解决线程安全的哈希表
 * - Map -> [过渡、熟悉] HashTable 或 Collections.synchronized[Sorted]Map；
 * - Map -> ConcurrentMap -> AbstractMap -> [核心] ConcurrentHashMap、ConcurrentSkipListMap。
 * 3）使用 [线程局部变量] 彻底解决线程安全问题的哈希表
 * - ThreadLocal.ThreadLocalMap。
 * 总结，基于 “热点分散” 思想（分段锁）提升并发访问效率的典型案例包括：
 * 1）[共享容器] ConcurrentHashMap，基于哈希函数（基于关键字 key 的数位分析法）为每个关键字 key 计算一个散列值，定位目标节点在 Node 数组中的位置（下标），然后以 cas “自旋” 方式原子操作每个哈希槽，当出现哈希冲突时，再使用 synchronized 内置锁互斥访问哈希槽中的的单向链表或红黑树，将并发粒度细化到了每个哈希槽，即解决了哈希表的线程安全问题，又最大限度地提升了并发效率。
 * 2）[共享计数器] LongAdder.Striped64，基于哈希函数（基于线程内部的 threadLocalRandomProbe 属性的随机数法）为每个线程计算一个随机散列值，从而将其定位到 Cell 数组的不同单元格（哈希槽）内，如果出现冲突，将采用 {开放地址法 -> 双重探测，避免内存泄露} 寻找下一个可用槽位，各个线程只对自己槽中的子 value 值进行 CAS 操作，如果要获得完整的 value 值，只需要将各个槽中的子 value 值累加起来即可。
 * 3）[共享变量] ThreadLocal.ThreadLocalMap，基于哈希函数（基于 threadLocalHashCode 常量的乘数 [getAndAdd()] 哈希法）为每个线程（基于threadLocals 强引用属性）所对应的关键字 key（被包装后的指向 ThreadLocal 实例的弱引用）计算一个散列值，定位到目标条目在 Entry 数组中的位置（下标），如果出现冲突，将采用 {开放地址法 -> 线性探测，避免内存泄露）} 寻找下一个可用槽位，各个线程只对自己槽中的 Entry 条目（局部变量）进行操作，从根本上解决了共享变量的线程安全问题。
 * 6. 利用 [哈希表] 处理海量数据 [去重、判重、TopK 频次统计] 问题。
 * 思想：先哈希映射，降低数据规模，然后再统计、排序，得到想要的结果。
 * 1）实现步骤：
 * a. [分而治之] 分析现有数据的规模，计算全部加载到内存中进行处理需要的总内存需求量，得出数据量太大，无法一次性全部加载到内存中进行处理的判断；
 * b. [分而治之] 基于 a. 中计算出来的内存总需求容量（total [总内存需求量] / memory [内存限制] = n），利用分治思想、哈希思想，采用哈希取模进行等价映射，将海量数据分割到不同的小文件（哈希槽）内 [同一种规律或同类数据会被分割到同一个小文件内]；
 * c. [HashMap<关注项, 重复次数>] 利用（内存）哈希表（HashSet [去重、判重]、HashMap [频次统计]）对每个小文件中的关注项进行频次统计；
 * d. [类似 MapReduce，排序、合并，得出最终结果] 使用高效率的排序算法（快速排序、堆排序、归并排序等）对存储在哈希表（HashMap [频次统计]）中的关注项（根据频次）进行排序，得出 TopK 关注项结果。
 * 2）常见面试题。
 * - [腾讯] 40 亿个 QQ 号，1G 内存，怎么去重？
 * - [腾讯] 搜索引擎的日志要记录所有查询串，有一千万条查询，不重复的不超过三百万，统计最热门的 10 条查询串，内存 < 1G，字符串长度 0~255。
 * - [360] 100 亿条记录的文本文件，如何取出重复数最多的前 10 条记录？
 * - [某大厂] 给定 a、b 两个文件，各自存放 50 亿个 url，每个 url 各占 64 字节，内存限制为 4G，请找出 a、b 文件中共同的 url。
 * 3）综合知识点：分治思想、哈希映射思想、位图、布隆过滤器、排序算法等。
 */